package com.xxd.algo.newcode.base02.class03;

public class Code01_KMP {

	// N >= M
	public static int getIndexOf(String s, String m) {
		if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
			return -1;
		}
		char[] str1 = s.toCharArray();
		char[] str2 = m.toCharArray();
		int x = 0; // str1 中比对到的位置
		int y = 0; // str2 中比对到的位置

		// next2 数组
		int[] next = getNextArray(str2);


		while (x < str1.length && y < str2.length) {
			if (str1[x] == str2[y]) {
				x++;
				y++;
			} else if (next[y] == -1) { // 说明这个y 一定是 被重置为0了
				// x 与 y不匹配，并且next[y] == -1 y = 0
				// str2中比对的位置已经无法往前跳了
				x++;
			} else { // y位置next数组的值不是 -1,y 会往前提
				y = next[y];
			}
		}

		// x 越界  或者  y越界了
		return y == str2.length ? x - y : -1;
	}

	public static int[] getNextArray(char[] ms) {
		if (ms.length == 1) {
			return new int[] { -1 };
		}
		int[] next = new int[ms.length];
		next[0] = -1;
		next[1] = 0;
		int i = 2;
		// next数组的位置
		int cn = 0;
		while (i < next.length) {
			if (ms[i - 1] == ms[cn]) {
				next[i++] = ++cn;
			} else if (cn > 0) { // 当前跳到cn位置的字符，和i-1位置的字符配不上
				cn = next[cn];
			} else {
				next[i++] = 0;
			}
		}
		return next;
	}

	public static void main(String[] args) {
		String str = "aaxaaaaxaak";
		String match = "aaxaaaaxaak";
		System.out.println(getIndexOf(str, match));
	}
}
